class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int r = matrix.size();
        if (r<1) {
            return false;
        }

        int c = matrix[0].size();
        if (c<1) {
            return false;
        }

        int i = 0;
        int j = c*r-1;
        int mid = 0;
        int val = 0;
        while(i<=j) {
            mid = i + (j-i)/2;
            val = getVal(matrix, mid, c);

            if (target == val) {
                return true;
            } else if (target < val) {
                j = mid-1;
            } else {
                i = mid+1;
            }
        }
        return false;
    }

    int getVal(vector<vector<int>>& matrix, int mid, int c) {
        int i = mid/c;
        int j = mid%c;
        return matrix[i][j];
    }
};

